package dataStructure.study.linkedList;

/**
 * Author: shangsf
 * Date: 2021/3/30 21:51
 * Description:链表实现LRU，
 * 当容量满了后，添加新数据时，最近最少使用的会被删掉
 */
public class LRU<T> {
    private long capacity;
    private long size;
    private Node<T> head;

    public LRU(long capacity){
        this.capacity=capacity;
    }

    public Node<T> getHead(){
        return head;
    }

    public void add(T data){
        if(size+1>capacity){
            removeLRU();
        }
        Node<T> node = new Node<T>(data);
        if(head==null){
            head=node;
        }else {
            node.next=head;
            head=node;
        }
        size++;
    }

    public void touch(T data){
        Node<T> prev=head;
        if(prev.data.equals(data)){
            return;
        }
        Node<T> node=prev.next;
        while (node!=null){
            if(node.data.equals(data)){
                prev.next=node.next;
                node.next=head;
                head=node;
                break;
            }
            prev=node;
            node=node.next;
        }
    }

    public void removeLRU(){
        Node<T> node=head;
        if(node==null){
            return;
        }
        int i=1;
        while (node!=null){
            if(size==i+1){
                node.next=null;
                size--;
                break;
            }
            node=node.next;
            i++;
        }
    }


    public static class Node<T>{
        public T data;
        public Node<T> next;

        public Node(T value){
            this.data=value;
        }
    }
}
